package arithmetic.mergearray;

import java.util.Arrays;

/**
 * @author zhangzg
 * @date 2022/10/12
 * 合并非递减顺序两个数组
 * nums1.length == m + n
 * nums2.length == n
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
 * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
 *
 */
public class Test {

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int m = 3;
        int[] nums2 = {2,5,6};
        int n = 3;
       // merge1(nums1,m,nums2,n);
        merge2(nums1,m,nums2,n);
    }

    public static void merge1(int[] nums1, int m, int[] nums2, int n){
        for (int i=0;i<n;i++){
            nums1[m++]=nums2[i];
        }
        Arrays.sort(nums1);
        System.out.println(Arrays.toString(nums1));
    }

    /**
     * 时间复杂度O(m+n)
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge2(int[] nums1, int m, int[] nums2, int n){
        int len=m+n;
        int[] arr=new int[len];
        int nums1Index=0;
        int nums2Index=0;
        for (int i=0;i<len;i++){
            if(nums1Index>=m){
                arr[i]=nums2[nums2Index++];
            }else if(nums2Index>=n){
                arr[i]=nums1[nums1Index++];
            }else if(nums1[nums1Index]>=nums2[nums2Index]){
                arr[i]=nums2[nums2Index++];
            }else if(nums1[nums1Index]<nums2[nums2Index]){
                arr[i]=nums1[nums1Index++];
            }
        }
        for(int i=0;i<arr.length;i++){
            nums1[i]=arr[i];
        }
        System.out.println(Arrays.toString(nums1));
    }

    public static void merge3(int[] nums1, int m, int[] nums2, int n){
        int k=m+n;
        int nums1Index=m-1;
        int nums2Index=n-1;
        for (int i=k-1;i>=0;i--){
            if(nums1Index<0){
                nums1[i]=nums2[nums2Index--];
            }else if(nums2Index<0){
                nums1[i]=nums1[nums1Index--];
            }else if(nums1[nums1Index]<nums2[nums2Index]){
                nums1[i]=nums2[nums2Index--];
            }else {
                nums1[i]=nums1[nums1Index--];
            }
        }
        System.out.println(Arrays.toString(nums1));
    }

}
